package dynamic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 转配线调度
 * 
 * @date 2012.4.17
 * @author Linxiaozhi
 * 
 */
public class Scheduling {
	int size = 6;
	int[][] t = new int[][] { { 2, 2, 3, 1, 3, 4, 3 }, { 4, 2, 1, 2, 2, 1, 2 } };
	int[][] f = new int[][] { { 7, 9, 3, 4, 8, 4 }, { 8, 5, 6, 4, 5, 7 } };
	int[][] s = new int[2][size + 1];
	int[][] a = new int[2][size + 1];

	void dynamic() {
		int i = 0;
		s[0][0] = f[0][0] + t[0][0];
		s[1][0] = f[1][0] + t[1][0];
		System.out.println("0:" + s[0][0] + "," + "1:" + s[1][0]);
		for (i = 1; i < size; i++) {
			int t1 = s[0][i - 1] + f[0][i];
			int t2 = s[1][i - 1] + t[1][i] + f[0][i];
			if (t1 > t2) {
				s[0][i] = t2;
				a[0][i] = 1;
			} else {
				s[0][i] = t1;
				a[0][i] = 0;
			}

			t1 = s[0][i - 1] + t[0][i] + f[1][i];
			t2 = s[1][i - 1] + f[1][i];
			if (t1 > t2) {
				s[1][i] = t2;
				a[1][i] = 1;
			} else {
				s[1][i] = t1;
				a[1][i] = 0;
			}
			System.out.println("0:" + s[0][i] + "," + "1:" + s[1][i]);
		}
		s[0][size] = s[0][size - 1] + t[0][size ];
		s[1][size] = s[1][size - 1] + t[1][size ];
	}

	void output() {
		int out;
		if (s[0][size] < s[1][size]) 
			out = 0;
		else 
			out = 1;
		System.out.println("output:" + s[out][size]);
		List<Integer> lists = new ArrayList<Integer>();
		lists.add(out+1);
		for (int i = size - 1; i > 0; i--) {
			// System.out.println(t+" ");
			out = a[out][i];
			lists.add(out+1);
		}
		Collections.reverse(lists);
		System.out.println(lists);
		System.out.println(Arrays.deepToString(a));
	}

	public static void main(String[] args) {
		Scheduling sched = new Scheduling();
		sched.dynamic();
		sched.output();

	}
}
